package 笔试题.博乐科技;

public class 花的最大面积 {

//    int[][] direction = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int rowSize;
    int colSize;

    public int maxAreaOfIsland(int[][] grid) {
        //沉岛算法
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return -1;
        }

        int max = Integer.MIN_VALUE;

        rowSize = grid.length;
        colSize = grid[0].length;

        for (int i = 0; i < rowSize; i++) {
            for (int j = 0; j < colSize; j++) {
                //剪枝
                if (grid[i][j] == 1) {
                    int res = dfs(grid, i, j);
                    max = res > max ? res : max;
                }
            }
        }

        return max;
    }

    public int dfs(int[][] grid, int i, int j) {
        if (i >= 0 && i < rowSize && j >= 0 && j < colSize && grid[i][j] == 1) {
            grid[i][j] = 0;
            return 1 + dfs(grid, i, j + 1) + dfs(grid, i + 1, j) + dfs(grid, i, j - 1) + dfs(grid, i - 1, j);
        }
        //terminator
        return 0;
    }
}
